package leetcode_900;

import java.util.Arrays;

/**
 * @author 周杨
 * 2018年11月9日 下午11:56:07 
 * BoatsToSavePeople_881.java  给定一个数组表示人的体重  要求一个船的限制载重  一艘船最多只能载两个人 问最少用多少船
 * description:用贪心 每次最优用双指针指向数组两头 排序数组 AC 69%
 */
public class BoatsToSavePeople_881 {
	public static void main(String[] args) {
		BoatsToSavePeople_881 test=new BoatsToSavePeople_881();
		System.out.println(test.numRescueBoats(new int[] {1,2}, 3));
	}
	
	
	public int numRescueBoats(int[] people, int limit) {
		 Arrays.sort(people);
	        int i = 0, j = people.length - 1;
	        int ans = 0;

	        while (i <= j) {
	            ans++;
	            if (people[i] + people[j] <= limit)
	                i++;
	            j--;
	        }

	        return ans;
    }
}
